package com.hanxiaozhang.no3algorithm.dynamicprogramming;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈数组的最长递减子序列〉
 *
 * @author hanxinghua
 * @create 2023/12/11
 * @since 1.0.0
 */
public class No3ArrayMaxLongDecSubArray {


    public static void main(String[] args) {

        int[] array = {9, 5, 4, 3, 2, 5, 4, 3, 1};
        int[] nums = {9, 4, 3, 2, 5, 4, 3, 2};


        method2(nums);
    }


    /**
     * 懵逼
     *
     * @param nums
     */
    private static void method2(int[] nums) {

        // 1. 构建状态表，其中第i个元素表示以第i个元素为结尾的最长递减子序列的长度。
        int[] dp = new int[nums.length];

        // 2. 初始化值，默认所有值的长度为1
        Arrays.fill(dp, 1);
        int maxLen = 1;

        // 4. 选择最优子结构（根据记忆表的值，计算每一步的最优值）
        // ** 从倒数第二个元素开始遍历
        for (int i = nums.length - 2; i >= 0; i--) {
            // ** 跟 i + 1元素开始比较
            for (int j = i + 1; j < nums.length; j++) {
                // 3. 构建状态转义方程：
                //  nums[i] > nums[j]时，dp[i] = Math.max(dp[i], dp[j] + 1)
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // System.out.println("第 " + i + "趟" + Arrays.toString(dp));
            maxLen = Math.max(maxLen, dp[i]);
        }

        System.out.println("最终状态表：" + Arrays.toString(dp));
        System.out.println("最长递减子序列的长度为：" + maxLen);
        System.out.print("最长递减子序列为：");
        for (int i = 0; i < nums.length; i++) {
            if (dp[i] == maxLen) {
                System.out.print(nums[i] + " ");
                maxLen--;
            }
        }
    }
}
